/**********************************************************

@description:
*File Name:graph.c
*Author: ydx
*mail: yudongxiang93@163.com
*Create Time: Wed 30 Apr 2025 10:53:12 PM CST
**********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
//vexs not gothrough, the arc is MAX
//vexs gothrough with itself, the arc is 0
//
#define MAX 32767
typedef struct graph{
	char *vexs;
	int **arcs;
	int vex_num,arc_num;
}graph;

graph * init_graph(int vex_num){
	graph *g=(graph*)malloc(sizeof(graph));
	g->vexs=(char*)malloc(sizeof(char)*vex_num);
	g->arcs=(int**)malloc(sizeof(int*)*vex_num);
	for(int i=0;i<vex_num;i++){
		g->arcs[i]=(int*)malloc(sizeof(int)*vex_num);
	}
	g->vex_num=vex_num;
	g->arc_num=0;
	return g;
}
void createGraph(graph *g,char *vexs,int* arcs){
	for(int i=0;i<g->vex_num;i++){
		g->vexs[i]=vexs[i];
		for(int j=0;j<g->vex_num;j++){
			g->arcs[i][j]=*(arcs+i*g->vex_num+j);
			if(g->arcs[i][j] != 0 && g->arcs[i][j] != MAX){
				g->arc_num++;
			}
		}
	}
	g->arc_num/=2;
}
void dfs(graph *g,int* visited,int index){
	printf("%c\t",g->vexs[index]);
	visited[index]=1;
	for(int i=0;i<g->vex_num;i++){
		if(g->arcs[index][i]>0 && g->arcs[index][i] != MAX && !visited[i]){
			dfs(g,visited,i);
		}
	}
}
void print_arr(int* arr,int len,char *name){
	printf("%s:",name);
	for(int i=0;i<len;i++){
		printf("%4d ",arr[i]);
	}
	printf("\n");
}
int get_min(int *S,int *D,int len){
	int min=MAX;
	int index;
	for(int i=0;i<len;i++){
		if(!S[i] && D[i]<min){
			min=D[i];
			index=i;
		}
	}
	return index;
}
void dijkstra(graph *g,int index){
	int *S =(int*)malloc(g->vex_num*sizeof(int));
	int *P =(int*)malloc(g->vex_num*sizeof(int));
	int *D =(int*)malloc(g->vex_num*sizeof(int));
	//init assit array:S
	for(int i=0;i<g->vex_num;i++){
		if(i==index)
			S[i]=1;
		else
			S[i]=0;
	}
	//init assit array:P
	for(int i=0;i<g->vex_num;i++){
		if(g->arcs[index][i] >0 && g->arcs[index][i] != MAX)
			P[i]=index;
		else
			P[i]=-1;
	}
	//init assit array:D
	for(int i=0;i<g->vex_num;i++){
		if(g->arcs[index][i] >0 && g->arcs[index][i] != MAX)
			D[i]=g->arcs[index][i];
		else
			D[i]=MAX;
		if(i==index)
			D[i]=0;
	}
	print_arr(S,g->vex_num,"S:");
	print_arr(P,g->vex_num,"P:");
	print_arr(D,g->vex_num,"D:");
	for(int i=0;i<g->vex_num-1;i++){
		int min_index=get_min(S,D,g->vex_num);
		S[min_index]=1;
		for(int j=0;j<g->vex_num;j++){
			if(!S[j] && D[min_index]+g->arcs[min_index][j]<D[j]){
				D[j]=D[min_index]+g->arcs[min_index][j];
				P[j]=min_index;
			}
		}
	}
	printf("after dijkstra:\n");
	print_arr(S,g->vex_num,"S:");
	print_arr(P,g->vex_num,"P:");
	print_arr(D,g->vex_num,"D:");
}


int main(){
	graph* g=init_graph(7);
	int arcs[49]={
		0,   12,MAX,MAX,MAX, 16, 14,
		12,   0, 10,MAX,MAX,  7,MAX,
		MAX, 10,  0,  3,  5,  6,MAX,
		MAX,MAX,  3,  0,  4,MAX,MAX,
		MAX,MAX,  5,  4,  0,  2,  8,
		16,   7,  6,MAX,  2,  0,  9,
		14, MAX,MAX,MAX,  8,  9,  0,
	};
	createGraph(g,"1234567",arcs);

	printf("dfs:");
	int *visited=(int*)malloc(sizeof(int)*g->vex_num);
	memset(visited,0,g->vex_num*sizeof(int));
	dfs(g,visited,0);
	printf("\n");
	dijkstra(g,0);
	printf("\n");
	
}
